Pillars

Memory limit: 256 MB

Byteasar holds the administrating manager position at a large warehouse. Anticipating a severe winter, he decided to install underfloor heating system in the warehouse.

Warehouse plan is a rectangle of even dimensions divided into individual square units. Most of the individual squares comprise warehouse space, but some of it is occupied by massive pillars providing additional constructional support for the warehouse structure. Each pillar occupies a square on the warehouse plan, composed of individual square units. Pillars are not arranged too densely-is known that any two of them are separated by at least 6 units (in Euclidean metric). Additionally, the centre of each pillar is located at least by 3 units away from each of the outer warehouse walls.

Heating will be accomplished by using one heating pipe installed under the floor of the warehouse. The pipe is to run through the centres of all individual square units except the square units occupied by pillars. Each pipe section must run parallel to one of the walls of the hall and the turns could be located only at the centres of the square units. The pipe must begin and end in the same place. At this point the cold water would be discharged outside and hot water fed into the pipe.

Byteasar has asked you to plan the pipe trajectory in the warehouse. To help you, he introduced rectangular coordinate system onto the warehouse plan, where the abscissae belong to the interval , and ordinates to the interval . The coordinates of the centres of all individual square units are numbers in the form dla ℕ.

Input

The first line of input contains three integers , and ( and and are even) indicating the warehouse dimensions and the number of the pillars. Each of the next lines contains two integers and (, ) denoting the coordinates of the centre of the -th pillar.

Output

In the first line of output your program should produce one word TAK (i.e., yes) or NIE (i.e., no) depending on whether the implementation of floor heating in line with Byteasar's requirements is achievable, or not. In case the answer is TAK, the second line should contain a description of the exemplary plan of the pipe trajectory in the form of a string of letters. We agree to assume that the beginning of the pipe is located at the point with the coordinates . Following parts of the pipe are marked as follows: transition by the vector is denoted by a letter G, by the vector is denoted by D, by the vector is denoted by P, and by the vector is denoted by L. In case there are multiple correct answers, your program should output any of them.

Example

For the input data:

12 6 2
3 3
9 3

the correct result is:

TAK
PPPPPPPPPPPGGGLDDLLLLLGPPGLLLDDLLLGGGPPPPPPPPPPGLLLLLLLLLLLDDDDD

Example output corresponds to the following figure:

Task author: Jakub Radoszewski.